package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class P797AllPathsFromSourceToTarget {
    public static void main(String[] args) {
        Solution solution = new P797AllPathsFromSourceToTarget().new Solution();
        
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] visited;
        public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
            List<List<Integer>> path = new ArrayList<>();
            for (int i = 0; i < graph.length; i++) {
                List<Integer> list = new ArrayList<>();
                int[] arr = graph[i];
                for (int j = 0; j < arr.length; j++) {
                    list.add(arr[j]);
                }
                path.add(list);
            }
            int size = path.size();
            int target = size - 1;
            int start = 0;
            visited = new boolean[size];
            List<Integer> clue = new ArrayList<>();
            clue.add(0);
            visited[0] = true;
            allPath(path,start,target,clue);
            return result;
        }

        private void allPath(List<List<Integer>> path, int start, int target, List<Integer> clue) {
            if (target == start) {
                result.add(new ArrayList<>(clue));
                return;
            }
            List<Integer> adj = path.get(start);
            for (int i = 0; i < adj.size(); i++) {
                Integer way = adj.get(i);
                if (!visited[way]) {
                    clue.add(way);
                    visited[way] = true;
                    allPath(path, way, target, clue);
                    visited[way] = false;
                    clue.remove(clue.size() - 1);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}